package advance.day08;

/**
 * 描述：
 *      求子数组累加和小于aim的最长子数组的长度，数组中的元素，可正可负可0
 * @author hl
 * @version 1.0
 * @date 2020/11/19 10:06
 */
public class LonggestSubArrayLessSum {
    public static int maxLengthAwesome(int[] arr, int aim){
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int n = arr.length;
        int[] min = new int[n];
        int[] minIndex = new int[n];
        min[n - 1] = arr[n - 1];
        minIndex[n - 1] = n- 1;
        for (int i = n - 2; i >= 0; i--) {
            if (min[i + 1] < 0) {
                min[i] = arr[i] + min[i + 1];
                minIndex[i] = minIndex[i + 1];
            }else{
                min[i] = arr[i];
                minIndex[i] = i;
            }
        }
        int r = 0;
        int sum = 0;
        int len = 0;
        for (int start = 0; start < n; start++) {
            while(r < n && sum + min[r] <= aim){
                sum += min[r];
                r = minIndex[r] + 1;
            }
            sum -= r > start ? arr[start] : 0;
            len = Math.max(len, r - start);
            r = Math.max(start + 1, r);
        }
        return len;
    }
    public static int maxLength(int[] arr, int k) {
        int[] h = new int[arr.length + 1];
        int sum = 0;
        h[0] = sum;
        for (int i = 0; i != arr.length; i++) {
            sum += arr[i];
            h[i + 1] = Math.max(sum, h[i]);
        }
        sum = 0;
        int res = 0;
        int pre = 0;
        int len = 0;
        for (int i = 0; i != arr.length; i++) {
            sum += arr[i];
            pre = getLessIndex(h, sum - k);
            len = pre == -1 ? 0 : i - pre + 1;
            res = Math.max(res, len);
        }
        return res;
    }

    public static int getLessIndex(int[] arr, int num) {
        int low = 0;
        int high = arr.length - 1;
        int mid = 0;
        int res = -1;
        while (low <= high) {
            mid = (low + high) / 2;
            if (arr[mid] >= num) {
                res = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return res;
    }

    // for test
    public static int[] generateRandomArray(int len, int maxValue) {
        int[] res = new int[len];
        for (int i = 0; i != res.length; i++) {
            res[i] = (int) (Math.random() * maxValue) - (maxValue / 3);
        }
        return res;
    }

    public static void main(String[] args) {
        for (int i = 0; i < 1000000; i++) {
            int[] arr = generateRandomArray(10, 20);
            int k = (int) (Math.random() * 20) - 5;
            if (maxLengthAwesome(arr, k) != maxLength(arr, k)) {
                System.out.println("oops!");
            }
        }
    }
}
